<!DOCTYPE html>
<html>
<head>
	<meta charset="utf-8" />
	<meta name="viewport" content="width=device-width, initial-scale=1">
	<title></title>
	<style type="text/css">
	*{
		margin: 0;
		padding: 0;
	}
	html,body{
		width: 100%;
		height: 100%;
		overflow: hidden;
		text-align: center;
	}
	#gameCanvas{
		/* border: 2px solid #ff3d17; */
		margin: 10px;
		position: relative;
	}
	#msg{
		width: 400px;
		height: 100px;
		border: 1px solid #888;
		margin-right: 10px;
		text-align: left;
		box-sizing: border-box;
		padding: 10px 20px;
		border: 16px solid #848bb8;
		border-radius: 4px;
	}
	.tip{
		display: inline-block;
		vertical-align: top;
	}
	span{
		color: #3f51a2;
		font-weight: bold;
	}
	.pannel{
		display: flex;
		justify-content: center;
		align-items: center;
	}
	.btns{
		display: flex;
		flex-flow: column nowrap;
		font-size: 14px;
		color: #fff;
	}
	.btn{
		width: 180px;
		height: 24px;
		line-height: 24px;
		padding: 2px 6px;
		border: 1px solid #848bb8;
		background-color: #848bb8;
		border-radius: 4px;
		cursor: pointer;
		user-select: none;
		margin: 2px 0;
		box-shadow: -2px 2px 4px #848bb899;
	}
	.btn:hover{
		background-color: #484d7a;
		box-shadow: -2px 2px 4px #848bb8;
	}
	.form{
		color: #fff;
		background-color: #848bb8;
		padding: 10px;
		margin-right: 10px;
		border-radius: 4px;
	}
	.size-btn{
		width: 80%;
		margin: 5px auto;
		background-color: #848bb8;
		color: #fff;
		cursor: pointer;
		user-select: none;
		border-radius: 4px;
	}
	.size-btn.act{
		background-color: #484d7a;
	}
	.size-btn:hover{
		background-color: #555b90;
	}
	</style>
</head>
<body>
<span class="tip">起点</span>
<canvas id="gameCanvas"></canvas>
<span>终点</span>
<div class="pannel">
<div class="form">
	<div>迷宫尺寸</div>
	<div id="size">
		<div data-index="0" class="size-btn">小</div>
		<div data-index="1" class="size-btn act">中</div>
		<div data-index="2" class="size-btn">大</div>
	</div>
	
</div>
<div id="msg"></div>
<div class="btns">
<div class="btn" onclick="noSkip()">完整动画</div>
<div class="btn" onclick="skipAnime(1)">跳过生成动画(寻路)</div>
<div class="btn" onclick="skipAnime()">跳过生成动画(不寻路)</div>
<div class="btn" onclick="skipFindAnime()">直达最终画面</div>
<div class="btn">画面上右键可下载图片</div>
</div>
</div>
<script type="text/javascript">
Array.prototype.forRound = function(fn,axis,self){
	var that = this, i = axis[0], j=axis[1];
	f(i-1,j-1);f(i-1,j);f(i-1,j+1);f(i,j-1);
	if(self){f(i,j)}f(i,j+1);f(i+1,j-1);f(i+1,j);f(i+1,j+1);
	function f(i,j){
		// 确保不访问非法内存
		if(i < 0 || i >= that.length || j < 0 || j >= that[0].length){
			return 0
		}
		fn(that[i][j],[i,j],that)
	}
}</script>
<script type="text/javascript">
!function(w,e){
	function Game(option){
		Object.assign(this,{
			el: "#gameCanvas",
			mainWidth: 0,
			mainHeight: 0,
			timer: null,
			side: 14,
			innerSide: 20,
			innerOffset: 0,
			map: [],
			nX: 41,
			nY: 41,
			animation: true,
			findAnime: true,
			findable: true,
		},option)
		this.init()
	}
	Game.prototype.expend = function(obj){Object.assign(this,obj)}
	Game.prototype.expend({
		// 初始化
		init(){
			this.canvas = e.querySelector(this.el)
			this.canvas.isUsed = true
			this.mainWidth = this.side*this.nX
			this.mainHeight = this.side*this.nY
			this.canvas.setAttribute("width",this.mainWidth)
			this.canvas.setAttribute("height",this.mainHeight)
			this.cx = this.canvas.getContext("2d")
			this.innerOffset = (this.side - this.innerSide) / 2
			this.addEvents()
			this.start()
		},
		// 绑定事件
		addEvents(){
			this.windowKeydown = evt => {
				var k = evt.key
				if(k === "a" || k === "A" || k === "ArrowLeft"){
					this.turn(-1,0)
				}else if(k === "d" || k === "D" || k === "ArrowRight"){
					this.turn(1,0)
				}else if(k === "w" || k === "W" || k === "ArrowUp"){
					this.turn(0,-1)
				}else if(k === "s" || k === "S" || k === "ArrowDown"){
					this.turn(0,1)
				}
			}
			w.addEventListener("keydown",this.windowKeydown)
		},
		start(){
			this.msg("开始生成迷宫")
			var rdmArrow = arrow => {
				for(var i = 0; i < 4; i++){
					var ar = Math.floor(Math.random()*4)
					var temp = arrow[i]
					arrow[i] = arrow[ar]
					arrow[ar] = temp
				}
			}
			var map = []
			var arrow = [[-2,0],[0,2],[2,0],[0,-2]]
			var curr = [1,1]
			var isBack = false
			var stack = []
			var tempCount = 0 // 初始未并入通道的节点个数(在如下循环中初始化)
			var bornComplete = false // 是否已经生成完成
			for(var i = 0; i < this.nY; i++){
				map[i] = []
				for(var j = 0; j < this.nX; j++){ // status: 0 墙, 1 未并入通道, 2 已并入通道
					if(!(i%2==0||j%2==0)){
						map[i][j] = 1
						tempCount++
					}else{
						map[i][j] = 0
					}
				}
			}
			var go = () => {
				// 统计全图 2 的个数是否等于 tempCount(检查全部节点是否已并入通道)
				var sum = 0
				for(var i = 0; i < this.nY; i++){
					for(var j = 0; j < this.nX; j++){
						if(!(i%2==0||j%2==0)){
							if(map[i][j]==2){
								sum++
							}
						}
					}
				}
				if(sum == tempCount){
					return true
				}
				map[curr[0]][curr[1]] = 2
				rdmArrow(arrow)
				isBack = true
				for(var i = 0; i < 4; i++){
					var ar = arrow[i]
					var y = curr[0]+ar[0] // 纵向一步以后的位置
					var x = curr[1]+ar[1] // 横向一步以后的位置
					var hy = curr[0]+ar[0]/2 // 纵向半步以后的位置
					var hx = curr[1]+ar[1]/2 // 横向半步以后的位置
					if(y<0 || y>this.nY-1 || x<0 || x>this.nX-1 || map[y][x]==2){
						continue // 如果一个方向不能走, 换一个方向
					}else{
						isBack = false // 能走
						stack.push([y,x]) // 压一个路径节点
						curr = [y,x] // 走一步
						// 把这一步路打通
						map[hy][hx] = 2
						break
					}
				}
				if(isBack){
					// 死路, 回头一步
					curr = stack.pop()
				}
				return false
			}
			// 寻路
			var road
			var findWay = () => {
				this.map = map
				// 克隆地图
				var mapClone = []
				for(var i = 0; i < this.nY; i++){
					mapClone[i] = []
					for(var j = 0; j < this.nX; j++){
						if(map[i][j]){
							mapClone[i][j] = 1
						}
					}
				}
				// 深度优先寻路
				road = [[1,1]] // 路线栈
				var isReach = false // 是否抵达终点
				arrow = [[0,1],[1,0],[-1,0],[0,-1]] // 右下上左
				curr = [1,1]
				var find = () => {
					if(curr[0] == this.nX-2 && curr[1] == this.nY-2){
						return true
					}
					mapClone[curr[0]][curr[1]] = 2
					isBack = true
					for(var i = 0; i < 4; i++){
						var ar = arrow[i]
						var y = curr[0]+ar[0] // 纵向一步以后的位置
						var x = curr[1]+ar[1] // 横向一步以后的位置
						if(mapClone[y][x]!=1){
							continue // 如果一个方向不能走, 换一个方向
						}else{
							if(isBack){
								road.push([curr[0],curr[1]])
							}
							isBack = false // 能走
							road.push([y,x]) // 压一个路径节点
							curr = [y,x] // 走一步
							break
						}
					}
					if(isBack){
						// 死路, 回头一步
						curr = road.pop()
					}
					return false
				}
				if(this.findAnime){
					var flag = 0
					this.fTimer = setInterval(()=>{
						flag = find()
						if(flag){
							clearInterval(this.fTimer)
							clearInterval(this.timer)
							this.msg("抵达终点")
						}
					},8)
				}else{
					var flag
					while(!flag){
						flag = find()
					}
				}
				
			}
			if(this.findable){
				if(this.animation){
					var flag = 0
					this.cTimer = setInterval(()=>{
						flag = go()
						if(flag){
							clearInterval(this.cTimer)
							this.msg("生成成功, 开始寻路")
							bornComplete = true
							findWay()
						}
					})
				}else{
					while(!go()){}
					this.msg("生成迷宫成功, 开始寻路")
					bornComplete = true
					findWay()
				}
			}else{
				while(!go()){}
				bornComplete = true
			}
			
			
			// 绘制
			this.cx.fillStyle = "#ddf"
			this.draw(() => {
				this.cx.fillStyle = "#848bb8"
				this.cx.fillRect(0,0,this.mainWidth,this.mainHeight)
				this.cx.fillStyle = "#fff"
				for(var i = 0; i < this.nY; i++){
					for(var j = 0; j < this.nX; j++){
						if(map[i][j] && map[i][j]!=1){
							this.cx.fillRect(j*this.side,i*this.side,this.side,this.side)
						}
					}
				}
				bornComplete && this.findable && road.forEach(s => {
					this.cx.fillStyle = "#0088ff44"
					this.cx.fillRect(s[1]*this.side,s[0]*this.side,this.side,this.side)
				})
			})
		},
		msg(){},
		// 销毁实例
		destroy(){
			this.timer && clearInterval(this.timer)
			this.fTimer && clearInterval(this.fTimer)
			this.cTimer && clearInterval(this.cTimer)
			this.cx.clearRect(0,0,this.mainWidth,this.mainHeight)
			this.canvas.isUsed = false
			w.removeEventListener("keydown",this.windowKeydown)
		},
		// 主绘制函数
		draw(frame,isSingle){
			this.timer && clearInterval(this.timer)
			var main = () => {
				this.cx.save()
				this.cx.clearRect(0,0,this.mainWidth,this.mainHeight)
				frame()
				this.cx.restore()
			}
			if(isSingle){
				main()
			}else{
				this.timer = setInterval(main,16)
			}
		}
	})
	w.Game = Game
}(window,document)
var sizeList = [[24,21],[14,41],[4,151]]
var sizeIndex = 1
var gameDemo = new Game({
	msg(v){
		msg.innerText = v
	}
})
size.onclick = function(e){
	var c = Array.from(e.currentTarget.children)
	var index = Number(e.target.dataset.index)
	c.forEach((el,i) => {
		el.classList[i===index?'add':'remove']('act')
	})
	sizeIndex = index
	noSkip()
}
function noSkip () {
	gameDemo.destroy()
	gameDemo = new Game({
		side: sizeList[sizeIndex][0],
		nX: sizeList[sizeIndex][1],
		nY: sizeList[sizeIndex][1],
		msg(v){
			msg.innerText = v
		}
	})
}
function skipAnime (findable) {
	gameDemo.destroy()
	gameDemo = new Game({
		side: sizeList[sizeIndex][0],
		nX: sizeList[sizeIndex][1],
		nY: sizeList[sizeIndex][1],
		animation: false,
		findable: findable ? true : false,
		msg(v){
			msg.innerText = v
		}
	})
}
function skipFindAnime () {
	gameDemo.destroy()
	gameDemo = new Game({
		side: sizeList[sizeIndex][0],
		nX: sizeList[sizeIndex][1],
		nY: sizeList[sizeIndex][1],
		animation: false,
		findAnime: false,
		msg(v){
			msg.innerText = v
		}
	})
}
</script>
</body>
</html>